package leetcode;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2022-02-17 22:44
 **/
public class LeetCode688 {

    static final int[][] DIRS = {{-2, -1}, {-2, 1}, {2, -1}, {2, 1}, {-1, -2}, {-1, 2}, {1, -2}, {1, 2}};

    public double knightProbability(int n, int k, int row, int column) {
        //dp[i][j][step] 表示骑士从棋盘上的点 (i,j) 出发，走了 step 步时仍然留在棋盘上的概率
        double[][][] dp = new double[n][n][k + 1];
        for (int i = 0; i <= k; i++) {
            for (int j = 0; j < n; j++) {
                for (int h = 0; h < n; h++) {
                    if (i == 0) {
                        dp[j][h][i] = 1;
                    } else {
                        for (int[] dir : DIRS) {
                            int nx = j + dir[0];
                            int ny = h + dir[1];
                            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                                dp[j][h][i] += dp[nx][ny][i - 1] / 8;
                            }
                        }
                    }
                }
            }
        }
        return dp[row][column][k];
    }

}
